package 翻转链表;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 翻转链表
 * @date 2022/10/15 14:02
 */

public class Demo206 {

    /**
     * Definition for singly-linked list.
     * */
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
    //双指针写法
    public ListNode reverseList(ListNode head) {
         //定义一个虚拟头节点,指针1
        ListNode pre=new ListNode(-1);
        //定义指针二的当前位置,指针2
        ListNode cur=head;
        while (cur!=null){
            //先记录cur下个节点位置
            ListNode temp=cur.next;
            //指针倒过来指
            cur.next=pre;
            //移动pre和cur
            pre=cur;
            cur=temp;
        }
        //遍历完后。头节点就是pre
        return pre;
    }

    //递归函数,先掌握双指针才能更好掌握递归写法
    public ListNode reverseList1(ListNode head) {
               //头节点和上个节点翻转
        return reverse(head,null);
    }

    private ListNode reverse(ListNode cur, ListNode pre) {
         if(cur==null){
             return pre;
         }else {
             //记录当前节点的下个节点
             ListNode temp=cur.next;
             //当前节点下个节点指向翻转
             cur.next=pre;
             //指针后移
             pre=cur;
             //递归两个节点再次翻转
             return reverse(temp,pre);
         }
    }


}
